import java.io.*;
import java.util.*;

/**
 * to solve the UVA problem MPI maelstrom 423
 * @author jjeske
 * status: ACCEPTED !
 *
 */
public class Main {	
	
		public static void main(String[] args){
			Main maelstrom = new Main();
			maelstrom.begin();
		}
		
		/* Sample Input

5
50
30 5
100 20 50
10 x x 10
*/
		private int N;
		private int[][] A;
		private boolean[] visitado;
		private int[] custo;
		private boolean[] broadcast;
		private static int INFINITO = 99999999;
				
		private void begin() {
			Scanner entrada = new Scanner(System.in);
			PrintStream saida = new PrintStream(System.out);		
			
			while (entrada.hasNext()) {
				N = entrada.nextInt();
				A = new int[N][N];
				visitado = new boolean[N];
				custo = new int[N];
				broadcast = new boolean[N];
				for (int i = 0; i < N; i++) {
					//				visitado[i] = false;
					//				custo[i] = INFINITO;
					broadcast[i] = false;
				}
				int aux;
				for (int i = 0; i < N; i++) {
					if (entrada.hasNextLine()) {
						String entradao = entrada.nextLine();
						String s[] = entradao.split(" ");
						for (int j = 0; j < s.length; j++) {
							try {
								aux = Integer.parseInt(s[j]);
							} catch (NumberFormatException e) {
								aux = INFINITO;
							}
							A[i][j] = aux;
							A[j][i] = aux;
						}
						;
					}
				}
				//corrigino o primeiro -9999 TODO: checkar porque isso acontece!
				A[0][0] = 0;
				
				FloydWarshall(); //executa caminhamentos
				
				
				int max = -1;
				for(int i=0; i<N; i++){
				    max = Math.max(max,A[0][i]);
				}
				
				saida.printf("%d\n", max);
			}
		}
		
		public void FloydWarshall(){
		  /* algoritmo de min-max de floyd */
		  for(int k=0;k<N;k++){
		    for(int i=0;i<N;i++){
		      for(int j=0;j<N;j++){
		        A[i][j] = Math.min( A[i][j] ,( A[i][k] + A[k][j]) );
		      }
		    }
		  }
		}
		
		
		
		//NAO funciona! -> troquei por floyd warshall !
		public int dijkstra(int INI, int FIM){
			  int i, k;
			  int aux = 0;
			  int minimo=0;

			  for(i=0 ; i<N ; i++) { 
			    visitado[i] = false;
			    custo[i] = INFINITO;
			  }

			  custo[INI] = 0;
			  visitado[INI] = true;
			  k = INI;

			  while(!visitado[FIM] && minimo!=INFINITO){
			    minimo = INFINITO;

			    for(i=0 ; i<N ; i++)
			      if(!visitado[i]){
				if(custo[i]>custo[k]+A[k][i]) /* relaxamento */
				  custo[i]=custo[k]+A[k][i];

				if(custo[i]<minimo){
				  minimo=custo[i];
			          aux=i;
				}
			      }

			    visitado[aux]=true;
			    k = aux;
			  }

			  if(visitado[FIM]) return custo[FIM];
			  	else return -1;
			  
			}		
}
